package leetcode.hot100;

import leetcode.tester.Tester;

import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 128. 最常连续序列
 * https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author Liu Yicong
 * @date 2025/9/28
 */
public class Hot3HashLongestConsecutive {

	public static void main(String[] args) {
		Object[][] inputs = {
				new Object[]{new int[]{100, 4, 200, 1, 3, 2},},
				new Object[]{new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1},},
				new Object[]{new int[]{1, 0, 1, 2},}
		};
		Integer[] outputs = {
				4,
				9,
				3
		};
		Tester.test(Tester.wrap(new Hot3HashLongestConsecutive()::longestConsecutive), inputs, outputs);
	}

	/**
	 * 首先将所有元素放入一个Set中去重
	 * 然后遍历Set中的每个元素，如果有则计为curr为比当前遍历的元素只增加1的数字，并且记录长度len + 1，直到找不到为止，记录maxLen。
	 */
	public int longestConsecutive(int[] nums) {
		int maxLen = 0;
		Set<Integer> s = Arrays.stream(nums).boxed().collect(Collectors.toSet());
		for (Integer num : s) {
			int curr = num + 1, len = 1;
			while (s.contains(curr)) {
				len++;
				curr++;
			}
			maxLen = Math.max(len, maxLen);
		}
		return maxLen;
	}

}
